#include <stdio.h>
#include <stdlib.h>

// 定义桶节点结构
typedef struct BucketNode {
    float value;
    struct BucketNode* next;
} BucketNode;

// 创建一个新的桶节点
BucketNode* createNode(float value) {
    // BucketNode* newNode = (BucketNode*)malloc(sizeof(BucketNode));
    // newNode->value = value;
    // newNode->next = NULL;
    // return newNode;
    BucketNode* newNode = (BucketNode*)malloc(sizeof(BucketNode));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// 将桶中的元素插入排序
void insertSorted(BucketNode** bucket, float value) {
    // BucketNode* newNode = createNode(value);
    // if (*bucket == NULL || (*bucket)->value >= value) {
    //     newNode->next = *bucket;
    //     *bucket = newNode;
    // } else {
    //     BucketNode* current = *bucket;
    //     while (current->next != NULL && current->next->value < value) {
    //         current = current->next;
    //     }
    //     newNode->next = current->next;
    //     current->next = newNode;
    // }

    BucketNode* newNode = createNode(value);
    if(*bucket == NULL || (*bucket)->value >= value)
    {
       newNode->next = *bucket;
       *bucket = newNode;
    }else {
        BucketNode* current = *bucket;
        while(current->next != NULL && current->next->value < value)
        {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;

    }
}

// 释放桶内存
void freeBucket(BucketNode* bucket) {
    // while (bucket != NULL) {
    //     BucketNode* temp = bucket;
    //     bucket = bucket->next;
    //     free(temp);
    // }
    while(bucket != NULL)
    {
        BucketNode * temp = bucket;
        bucket = bucket->next;
        free(temp);
    }
}

// 桶排序函数
void bucketSort(float arr[], int n) {
    // 创建n个桶
    // BucketNode** buckets = (BucketNode**)malloc(n * sizeof(BucketNode*));
    // for (int i = 0; i < n; i++) {
    //     buckets[i] = NULL;
    // }
    BucketNode** buckets = (BucketNode**)malloc(n*sizeof(BucketNode*));
    for(int i = 0; i < n; i++)
    {
        buckets[i] = NULL;
    }
    // 将元素分配到桶中
    // for (int i = 0; i < n; i++) {
    //     int bucketIndex = n * arr[i]; // 假设数组元素在[0, 1)范围内
    //     insertSorted(&buckets[bucketIndex], arr[i]);
    // }
    for(int i = 0; i < n; i++)
    {
        int bucketIndex = n*arr[i];
        insertSorted(&buckets[bucketIndex],arr[i]);
    }

    // 将桶中的元素取出放回数组
    // int index = 0;
    // for (int i = 0; i < n; i++) {
    //     BucketNode* current = buckets[i];
    //     while (current != NULL) {
    //         arr[index++] = current->value;
    //         current = current->next;
    //     }
    //     freeBucket(buckets[i]);
    // }
    int index = 0;
    for(int i = 0; i < n;i++)
    {
        BucketNode* current = buckets[i];
        while(current != NULL)
        {
            arr[i] = current->value;
            current = current->next;
        }
        freeBucket(buckets[i]);
    }
    // 释放桶数组内存
    free(buckets);
}

// 测试桶排序
int main() {
    float arr[] = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前: \n");
    for (int i = 0; i < n; i++) {
        printf("%f ", arr[i]);
    }
    printf("\n");

    bucketSort(arr, n);

    printf("排序后: \n");
    for (int i = 0; i < n; i++) {
        printf("%f ", arr[i]);
    }
    printf("\n");

    return 0;
}
